Binary AIFV codes are lossless codes that generalize the class ofinstantaneous FV codes. The code uses two code trees and assigns source symbolsto incomplete internal nodes as well as to leaves. AIFV codes are empiricallyshown to attain better compression ratio than Huffman codes. Nevertheless, anupper bound on the redundancy of optimal binary AIFV codes is only known to be1, which is the same as the bound of Huffman codes. In this paper, the upperbound is improved to 1/2, which is shown to coincide with the worst-caseredundancy of the codes. Along with this, the worst-case redundancy is derivedin terms of $p_{\max}\geq$1/2, where $p_{\max}$ is the probability of the mostlikely source symbol. Additionally, we propose an extension of binary AIFVcodes, which use $m$ code trees and allow at most $m$-bit decoding delay. Weshow that the worst-case redundancy of the extended binary AIFV codes is $1/m$for $m \leq 4.$
展开▼
机译：二进制AIFV代码是无损代码，可概括瞬时FV代码的类别。该代码使用两个代码树，并将源符号分配给不完整的内部节点以及叶子。根据经验显示，AIFV码比霍夫曼码具有更好的压缩率。然而，最优二进制AIFV码冗余的上限仅被知道为1，这与霍夫曼码的界限相同。本文将上限提高到1/2，这与代码的最坏情况下的冗余相吻合。随之，以$ p _ {\ max} \ geq $ 1/2得出最坏情况的冗余，其中$ p _ {\ max} $是最可能的源符号的概率。此外，我们提出了二进制AIFVcode的扩展，该扩展使用$ m $代码树并允许最多$ m $位的解码延迟。我们显示扩展的二进制AIFV代码的最坏情况下的冗余度是$ m $ 1 \ m $ leq 4. $
展开▼
